Algorithm

數獨是一個經典的數字拼圖遊戲，目標是填充一個9x9的方格，使每一列、每一行和每一個3x3的小方格內都包含1到9的數字，並且不重複。

解數獨的方法有以下類型：

檢查行和列

檢查每一行和每一列，確保它們都包含1到9的數字，並且沒有重複的數字。如果你看到一個缺失的數字，就試著填入它。

檢查小方格

檢查每個3x3的小方格內是否包含1到9的數字，並且沒有重複的數字。如果你發現一個缺失的數字，就試著填入它。

唯一數字法

當某一個單元格的可能數字中只有一個數字時，你可以確定這個數字就是該單元格的解。這種情況下，填入這個數字。

候選數字法

如果一個單元格有多個可能的數字，則你可以使用候選數字法。這意味著你需要仔細檢查每一個單元格，並根據行、列和小方格的已知數字來排除一些數字，從而縮小候選數字的範圍。

回溯法

這是一種遞迴的方法，你嘗試填入一個數字，然後繼續解題，如果後來發現矛盾，就回溯到之前的步驟並嘗試不同的數字，直到找到正確的解為止。

Code

// Sudoku in Kotlin

fun solveSudoku(board: Array<CharArray>): Boolean {
    for (row in 0 until 9) {
        for (col in 0 until 9) {
            if (board[row][col] == '.') {
                for (num in '1'..'9') {
                    if (isValid(board, row, col, num)) {
                        board[row][col] = num
                        if (solveSudoku(board)) {
                            return true
                        }
                        board[row][col] = '.' // Undo the current placement and try the next number
                    }
                }
                return false // No valid number found, backtrack
            }
        }
    }
    return true // Sudoku solved
}

fun isValid(board: Array<CharArray>, row: Int, col: Int, num: Char): Boolean {
    val subgridRow = 3 * (row / 3)
    val subgridCol = 3 * (col / 3)
    
    // Check row and column
    for (i in 0 until 9) {
        if (board[row][i] == num || board[i][col] == num) {
            return false
        }
    }
    
    // Check subgrid
    for (i in subgridRow until subgridRow + 3) {
        for (j in subgridCol until subgridCol + 3) {
            if (board[i][j] == num) {
                return false
            }
        }
    }
    
    return true
}

fun main() {
    val sudokuBoard = arrayOf(
        charArrayOf('5', '3', '.', '.', '7', '.', '.', '.', '.'),
        charArrayOf('6', '.', '.', '1', '9', '5', '.', '.', '.'),
        charArrayOf('.', '9', '8', '.', '.', '.', '.', '6', '.'),
        charArrayOf('8', '.', '.', '.', '6', '.', '.', '.', '3'),
        charArrayOf('4', '.', '.', '8', '.', '3', '.', '.', '1'),
        charArrayOf('7', '.', '.', '.', '2', '.', '.', '.', '6'),
        charArrayOf('.', '6', '.', '.', '.', '.', '2', '8', '.'),
        charArrayOf('.', '.', '.', '4', '1', '9', '.', '.', '5'),
        charArrayOf('.', '.', '.', '.', '8', '.', '.', '7', '9')
    )

    // Print the unsolved sudoku board
    println("Unsolved sudoku:")
    for (row in sudokuBoard) {
        println(row.joinToString(" "))
    }

    if (solveSudoku(sudokuBoard)) {
        println("Sudoku solved:")
        for (row in sudokuBoard) {
            println(row.joinToString(" "))
        }
    } else {
        println("No solution exists.")
    }
}

Terminal 輸出畫面

Unsolved sudoku:
5 3 . . 7 . . . .
6 . . 1 9 5 . . .
. 9 8 . . . . 6 .
8 . . . 6 . . . 3
4 . . 8 . 3 . . 1
7 . . . 2 . . . 6
. 6 . . . . 2 8 .
. . . 4 1 9 . . 5
. . . . 8 . . 7 9
Sudoku solved:
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9

所有 Code 可以在 Github 找到 ～

感謝各位讀者，我們明天見！